package org.arithmetic.array;

import java.util.HashMap;
import java.util.Map;

/**
 * Created by LUOLIANG on 2016/9/3.
 * 春节期间小明使用微信收到很多个红包，非常开心。在查看领取红包记录时发现，某个红包金额出现的次数超过了红包总数的一半。请帮小明找到该红包金额。写出具体算法思路和代码实现，要求算法尽可能高效。
 * 给定一个红包的金额数组gifts及它的大小n，请返回所求红包的金额。
 * 若没有金额超过总数的一半，返回0。
 */
public class Gift {
    public static int getValue(int[] gifts, int n) {
        // write code here
        int k = n / 2;
        Map<Integer, Integer> map = new HashMap();
        for (int i = 0; i < gifts.length; i++) {
            Integer count = 0;
            if (map.containsKey(gifts[i])) {
                count = map.get(gifts[i]);
                count++;
                if (count >= k) {
                    return gifts[i];
                }
            }
            map.put(gifts[i], count);
        }

        return 0;
    }

    public static void main(String[] args) {
        int[] num = {1, 2, 3, 2, 2, 3, 3, 2, 2};

        System.out.println(getValue(num, num.length));
    }
}
